#include <stdio.h>

void binaryInsertionSort(int arr[], int n)
{
    int i, j, key, low, high, mid, pos;

    for (i = 1; i < n; i++)
    {
        key = arr[i]; // 当前需要插入的元素
        low = 0;
        high = i - 1;

        printf("Processing element %d: %d\n", i, key); // 处理当前元素

        // 使用二分查找确定插入位置
        while (low <= high)
        {
            mid = (low + high) / 2;
            if (key < arr[mid])
            {
                high = mid - 1;
            }
            else
            {
                low = mid + 1;
            }
        }

        pos = low; // 找到的插入位置

        // 将大于key的元素后移
        for (j = i - 1; j >= pos; j--)
        {
            arr[j + 1] = arr[j];
        }

        // 插入key到正确位置
        arr[pos] = key;

        // 打印当前排序步骤
        printf("Step %d: ", i);
        for (j = 0; j < n; j++)
        {
            printf("%d ", arr[j]);
        }
        printf("\n\n");
    }
}

int main()
{
    int arr[] = {64, 25, 12, 22, 11};
    int n = sizeof(arr) / sizeof(arr[0]);
    int i;

    printf("Original array: "); // 原始数组
    for (i = 0; i < n; i++)
    {
        printf("%d ", arr[i]);
    }
    printf("\n\n");

    binaryInsertionSort(arr, n); // 调用折半插入排序函数

    printf("\nSorted array: "); // 排序后的数组
    for (i = 0; i < n; i++)
    {
        printf("%d ", arr[i]);
    }
    printf("\n");

    return 0;
}